//中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。 
//
// 
// 例如 arr = [2,3,4] 的中位数是 3 。 
// 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 
// 
//
// 实现 MedianFinder 类: 
//
// 
// MedianFinder() 初始化 MedianFinder 对象。 
// void addNum(int num) 将数据流中的整数 num 添加到数据结构中。 
// double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10⁻⁵ 以内的答案将被接受。 
// 
//
// 示例 1： 
//
// 
//输入
//["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
//[[], [1], [2], [], [3], []]
//输出
//[null, null, null, 1.5, null, 2.0]
//
//解释
//MedianFinder medianFinder = new MedianFinder();
//medianFinder.addNum(1);    // arr = [1]
//medianFinder.addNum(2);    // arr = [1, 2]
//medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
//medianFinder.addNum(3);    // arr[1, 2, 3]
//medianFinder.findMedian(); // return 2.0 
//
// 提示: 
//
// 
// -10⁵ <= num <= 10⁵ 
// 在调用 findMedian 之前，数据结构中至少有一个元素 
// 最多 5 * 10⁴ 次调用 addNum 和 findMedian 
// 
//
// Related Topics 设计 双指针 数据流 排序 堆（优先队列） 👍 872 👎 0


package LeetCode.editor.cn;

import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * @author ldltd
 * @date 2023-09-13 15:29:09
 * @description 295.数据流的中位数
 */
public class FindMedianFromDataStream{
	 public static void main(String[] args) {
	 	 //测试代码

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class MedianFinder {
         /*一个大堆一个小堆
         * 大堆存储小于中位数的部分
         * 小堆存储大于中位数的部分*/
         PriorityQueue<Integer> maxheap;
         PriorityQueue<Integer> minheap;

    public MedianFinder() {
        minheap=new PriorityQueue<>();
        maxheap=new PriorityQueue<>((o1,o2)->o2-o1);
    }
    
    public void addNum(int num) {
      /*  //先加入大堆,调整耗时，不好
        maxheap.add(num);
        //将大堆的顶部加入小堆
        minheap.add(maxheap.remove());
        //如果小堆的数量大于大堆了，把小堆的顶部放回大堆
        *//*1223  4556  来了2
        * 12223  4556
        * 1222 34556
        * 12223 4556 *//*
        if(minheap.size()>maxheap.size())
            maxheap.add(minheap.remove());*/

        if (maxheap.isEmpty() || num <= maxheap.peek()) {
            maxheap.offer(num);
            if (minheap.size() + 1 < maxheap.size()) {
                minheap.offer(maxheap.poll());
            }
        } else {
            minheap.offer(num);
            if (minheap.size() > maxheap.size()) {
                maxheap.offer(minheap.poll());
            }
        }
    }
    
    public double findMedian() {
        if(maxheap.size()==minheap.size()){
            return (maxheap.peek()+minheap.peek())/2.0;
        }
        return maxheap.peek();
    }
}
/*有序集合+双指针*/
    class MedianFinder1 {
        //存储各个数字出现的次数
        TreeMap<Integer,Integer> nums;
        //当前集合的大小
        int n;
        //存储中位数的左右不分，0是数字，1是次数
        int [] l;
        int[] r;

        public MedianFinder1() {
        nums=new TreeMap<>();
        n=0;
        l=new int[2];
        r=new int[2];
        }

        public void addNum(int num) {
            //加入集合，赋值1或者次数+1
         nums.put(num,nums.getOrDefault(num,0)+1);
         //有序集合中还没有的时候，让左右都赋值为num，次数为1
         if(n==0){
             l[0]=r[0]=num;
             l[1]=r[1]=1;
         }else if((n&1)!=0){
             //为奇数的时候
             //lr都指向中位数，如果Num小于中位数，则让l左移，否则r右移即可
             if(num<l[0]){
                 decrease(l);
             }else {
                 increase(r);
             }
         }else {
             //偶数的时候
             //加入后变成基数，且加入的数在lr中
             //lr都向中间移动
             if(num>l[0]&&num<r[0]){
                 increase(l);
                 decrease(r);
                 //如果大于r，则l右移
             }else if(num>=r[0]){
                 increase(l);
             }else {
                 //如果小于l，则r左移，l也需要右移，这里直接复制
                 decrease(r);
                 //将右半的数据赋值到左半
                 System.arraycopy(r,0,l,0,2);
             }
         }
         n++;
        }

        public double findMedian() {
            return (l[0]+r[0])/2.0;
        }
        //增加l或者r，将iterator数组的元素值移到下一个整数
        //如果次数超过了该整数出现的次数，那么移到到下一个整数值
        private void increase(int [] iterator){
            //右移可能和原先的数相等，也可能不相等，如果不相等++后就和集合中存储的出现次数不同
            //寻找下一个位置
            iterator[1]++;
            if(iterator[1]>nums.get(iterator[0])){
                //ceilingKey 方法用于查找并返回大于或等于给定键 key 的最小键
                iterator[0]=nums.ceilingKey(iterator[0]+1);
                iterator[1]=1;
            }
        }
        private void decrease(int [] iterator){
            //同理，左移可能相同，但如果左移到头了，就要找上一个整数
            iterator[1]--;
            if(iterator[1]==0){
                //floorKey 方法用于查找并返回小于或等于给定键 key 的最大键。
                iterator[0]=nums.floorKey(iterator[0]-1);
                iterator[1]= nums.get(iterator[0]);
            }
        }
    }

    /*如果数据样例百分之99在1~100之间
    * 把超过的部分用有序集合保存起来*/
    class MedianFinder3 {
        TreeMap<Integer, Integer> head = new TreeMap<>(), tail = new TreeMap<>();
        int[] arr = new int[101];
        int a, b, c;
        public void addNum(int num) {
            if (num >= 0 && num <= 100) {
                arr[num]++;
                b++;
            } else if (num < 0) {
                head.put(num, head.getOrDefault(num, 0) + 1);
                a++;
            } else if (num > 100) {
                tail.put(num, tail.getOrDefault(num, 0) + 1);
                c++;
            }
        }
        public double findMedian() {
            int size = a + b + c;
            if (size % 2 == 0) return (find(size / 2) + find(size / 2 + 1)) / 2.0;
            return find(size / 2 + 1);
        }
        int find(int n) {
            if (n <= a) {
                for (int num : head.keySet()) {
                    n -= head.get(num);
                    if (n <= 0) return num;
                }
            } else if (n <= a + b) {
                n -= a;
                for (int i = 0; i <= 100; i++) {
                    n -= arr[i];
                    if (n <= 0) return i;
                }
            } else {
                n -= a + b;
                for (int num : tail.keySet()) {
                    n -= tail.get(num);
                    if (n <= 0) return num;
                }
            }
            return -1; // never
        }
    }


/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
